package william.string;

import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/4/26
 * @description <a href="https://leetcode.cn/problems/simplify-path/description/">...</a>
 */
public class Leetcode71_简化路径 {
    public static void main(String[] args) {
        Leetcode71_简化路径 s = new Leetcode71_简化路径();
        s.simplifyPath("/..");
    }

    /**
     * 借助一个队列实现
     * 首先将path按照'/'进行切分
     * 然后遍历切分后的元素,按照不同情况,进行入队/出队操作
     * 最后遍历队列,拼接最终结果
     * <p>
     * 时间复杂度O(N) 遍历字符串O(N)+遍历队列O(N)
     * 空间复杂度O(N) 额外申请了一个队列,长度为N
     */
    public String simplifyPath(String path) {
        //边界条件校验
        if (path == null || path.isEmpty()) {
            throw new IllegalArgumentException("invalid input!");
        }

        //将path按照'/'进行切分
        String[] paths = path.split("/");

        //借助队列,保存path元素
        LinkedList<String> queue = new LinkedList<>();

        //遍历切分后的元素,按照不同情况,进行入队/出队操作
        for (String p : paths) {
            if (".".equals(p)) { //当前路径,直接跳过
                continue;
            }
            if ("..".equals(p)) {    //上级路径,移除队尾元素
                if (!queue.isEmpty()) {
                    queue.removeLast();
                }
                continue;
            }

            //将元素入队
            if (!p.isEmpty()) {
                queue.addLast(p);
            }
        }

        //遍历队列,拼接完整路径
        if (queue.isEmpty()) {
            return "/";
        }

        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            result.append("/");
            result.append(queue.removeFirst());
        }

        //返回结果
        return result.toString();
    }
}
